package dynamic;
import org.junit.Test;
import java.util.*;
import utils.ArrayGenerator;
//根本就不是递归和动态规划题，是前缀和的题
public class Ex560 {
    class Solution {//错误，没有考虑去掉重复的解
        public int subarraySum(int[] nums, int k) {
            dfs(nums, k, 0, 0);
            return res.size();
        }
        List<String> res = new ArrayList<>();
        public int dfs(int[] nums, int target, int idx, int cur) {
            if (cur == target) return 1;
            if (cur > target || idx == nums.length) return 0;
            //cur + nums[idx] 表示继续探查，cur = 0表示重新开始探查
            int res = dfs(nums, target, idx + 1, cur + nums[idx]) + dfs(nums, target, idx + 1, 0);
            return res;
        }   

        public int subarraySum2(int[] nums, int k) {
            int len = nums.length, sum = 0;
            for (int i = 0; i < len; i++) sum += nums[i];
            int[][] f = new int[len + 1][sum + 1];
            // f[len][k] = 1;
            for (int i = 0; i <= len; i++) f[i][k] = 1;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= sum; j++){
                    if (j == k) continue;
                    f[i][j] = f[i + 1][0];
                    if (j + nums[i] <= sum) {
                        f[i][j] += f[i + 1][j + nums[i]];
                    }
                }
            }
            for (int i = 0; i < f.length; i++) System.out.println(Arrays.toString(f[i]));
            return f[0][0];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums1 = {1,1,1};
        int[] nums = new int[]{1,2,3};
        System.out.println(s.subarraySum2(nums1, 2));  
        System.out.println(s.subarraySum(nums, 3));
    }

    class Solution2 {//尝试投机
        public int subarraySum(int[] nums, int k) {
            int sum = 0, len = nums.length;
            for (int i = 0; i < len; i++) sum += nums[i];
            
            dfs(nums, k, 0, 0, new LinkedList<>());
            System.out.println(res);
            return res.size();
        }

        List<String> res = new ArrayList<>();
        public int dfs(int[] nums, int target, int idx, int cur, Deque<Integer> path) {
            if (cur == target) {
                res.add(path.toString());
                return 1;
            }
            if (cur > target || idx == nums.length) return 0;
            //cur + nums[idx] 表示继续探查，cur = 0表示重新开始探查
            // int res = dfs(nums, target, idx + 1, cur + nums[idx]) + dfs(nums, target, idx + 1, 0);
            int res = 0;
            path.addLast(idx);
            res += dfs(nums, target, idx + 1, cur + nums[idx], path);
            path.removeLast();
            res +=  dfs(nums, target, idx + 1, 0, new LinkedList<>());
            return res;
        }   

        public int subarraySum2(int[] nums, int k) {
            int len = nums.length, sum = 0;
            for (int i = 0; i < len; i++) sum += nums[i];
            int[][] f = new int[len + 1][sum + 1];
            // f[len][k] = 1;
            for (int i = 0; i <= len; i++) f[i][k] = 1;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= sum; j++){
                    if (j == k) continue;
                    f[i][j] = f[i + 1][0];
                    if (j + nums[i] <= sum) {
                        f[i][j] += f[i + 1][j + nums[i]];
                    }
                }
            }
            for (int i = 0; i < f.length; i++) System.out.println(Arrays.toString(f[i]));
            return f[0][0];
        }
    }

    @Test
    public void test2() {
        Solution2 s = new Solution2();
        int[] nums1 = {1,1,1};
        int[] nums = new int[]{1,2,3};
        System.out.println(s.subarraySum(nums1, 2));  
        System.out.println(s.subarraySum(nums, 3));
    }

    class Solution3 {
        //暴力解法，枚举左右边界，在进行累加
        public int subarraySum(int[] nums, int k) {
            int len = nums.length, sum, count = 0;
            for (int i = 0; i < len; i++) {
                sum = 0;
                for (int j = i; j < len; j++) {
                    sum += nums[j];
                    if (sum == k) count++;
                }
            }
            return count;
        }

        //缓存所有前缀和，为了防止nums[0] == k, 将-1位设置前缀和为0，则preSum[0] - preSum[-1] == nums[0] == k
        //preSum[i] = nums[0] + nums[1] + ... + nums[i]
        //使得某一段[i, j]连续和为k，则preSum[j] - preSum[i] == k
        public int subarraySum2(int[] nums, int k) {
            Map<Integer, List<Integer>> map = new HashMap<>(); //KEY:前缀和， VAL：下标集合
            int sum = 0, count = 0;
            map.put(0, new ArrayList<>(){{add(-1);}});
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (map.containsKey(sum - k)) count += map.get(sum - k).size();
                if (!map.containsKey(sum)) map.put(sum, new ArrayList<>());
                map.get(sum).add(i);
            }
            return count;
        }
    }

    @Test
    public void test3() {
        Solution3 s = new Solution3();
        int[] nums1 = {1,1,1};
        int[] nums = new int[]{1,2,3};
        int[] nums2 = {1,-1,0};
        // System.out.println(s.subarraySum2(nums1, 2));  
        // System.out.println(s.subarraySum2(nums, 3));
        System.out.println(s.subarraySum2(nums2, 0));
        // int[] nums3 =  ArrayGenerator.getArray(-1000, 1000, 20000);
        // System.out.println(Arrays.toString(nums3));
    }
}
